/*
** Definitions of AVL APIs based on threaded height-balanced tree
** implementation. Threaded AVL trees provide fast access, O(log N),
** to data nodes AND allow efficient, O(1), sequential access.
*/

#ifndef __TAVL_H__
#define __TAVL_H__ 1

#ifdef __cplusplus
extern "C" {
#endif				/* __cplusplus */

/* Include files. */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/**************************************************************************
** TAVL library public functions, types & constants.
**************************************************************************/

/*   See note below
     ... recommended that TAVL_USE_BIT_FIELDS remain commented out,
     ... both for efficiency (speed) and universiality.
#define TAVL_USE_BIT_FIELDS
*/

	typedef int (*tavl_comparison_func) (void *tavl_a, void *tavl_b, void *tavl_param);
	typedef void *(*key_of) (void *DataObject);
	typedef void *(*make_item) (void *DataObject);
	typedef void (*free_item) (void *DataObject);
	typedef void *(*copy_item) (void *Destination_DataObject, void *Source_DataObject);
	typedef void *(*alloc) (size_t);
	typedef void (*dealloc) (void *);

	typedef struct tavlnode *TAVL_nodeptr;
	typedef struct tavltree *TAVL_treeptr;

/* Constants for "replace" parameter of "tavl_insert" */
#define REPLACE     1
#define NO_REPLACE  0

/* prototypes */

	TAVL_treeptr tavl_init(int (*compare) (void *, void *, void *),	/* compares identifiers */
			       void *(*key_of) (void *DataObject), void *(*make_item) (void *DataObject),
			       void (*free_item) (void *DataObject), void *(*copy_item) (void *Destination_DataObject,
											 void *Source_DataObject),
			       void *(*alloc) (size_t), void (*dealloc) (void *), void *paramP);
	/*
	   Returns pointer to empty tree on success, NULL if insufficient
	   memory.  The function pointers passed to "tavl_init" determine
	   how that instance of tavl_tree will behave & how it will use
	   dynamic memory.

	   parameters-
	   compare:      Compares identifiers, same form as "strcmp".
	   key_of:       Gets pointer to a data object's identifier.
	   make_item:    Creates new data object that is a copy of
	   *DataObject.
	   free_item:    Complements make_item. Releases any memory
	   allocated to DataObject by "make_item".
	   copy_item:    Copies data object *Source to buffer *Dest
	   alloc:        Memory allocator.
	   dealloc:      Deallocates dynamic memory - complements
	   "alloc"
	 */

	TAVL_nodeptr tavl_insert(TAVL_treeptr tree, void *item, int replace);
	/*
	   Using the user supplied "key_of" & "compare" functions,
	   *tree is searched for a node which matches *item. If a
	   match is found, the new item replaces the old if & only
	   if replace != 0.  If no match is found the item is
	   inserted into *tree.  "tavl_insert" returns a pointer to
	   the node inserted or found, or NULL if there is not enough
	   memory to create a new node and copy "item".  Uses functions
	   "key_of" and "compare" for comparisons and to retrieve
	   identifiers from data objects, "make_item" to create a copy
	   of "item", "alloc" to get memory for the new tree node, and
	   "dealloc" if "make_item" fails.
	 */
	void *tavl_delete(TAVL_treeptr tree, void *key);
	/*
	   Delete node identified by "key" from *tree.
	   Returns a Data-Pointer if found and deleted, NULL if not found.
	   Uses "compare", "key_of", "free_item" and "dealloc".
	   See function tavl_init.
	 */

	void tavl_destroy(TAVL_treeptr tree);
	/*
	   Destroy the tree. Uses functions "free_item" and "dealloc"
	   to restore pool memory used. See function tavl_init.
	 */

	TAVL_nodeptr tavl_find(TAVL_treeptr tree, void *key);
	/*
	   Returns pointer to node which contains data item
	   in *tree whose identifier equals "key". Uses "key_of"
	   to retrieve identifier of data items in the tree,
	   "compare" to compare the identifier retrieved with
	   *key.  Returns NULL if *key is not found.
	 */

/********************************************************************
    Following three functions allow you to treat tavl_trees as a
    doubly linked sorted list with a head node.  This is the point
    of threaded trees - it is almost as efficient to move from node
    to node or back with a threaded tree as it is with a linked list.
*********************************************************************/

	TAVL_nodeptr tavl_reset(TAVL_treeptr tree);
	/*
	   Returns pointer to begin/end of *tree (the head node).
	   A subsequent call to tavl_succ will return a pointer
	   to the node containing first (least) item in the tree;
	   just as a call to tavl_pred would return the last
	   (greatest).  Pointer returned can only be used a parameter
	   to "tavl_succ" or "tavl_pred" - the head node contains no
	   user data.
	 */

	TAVL_nodeptr tavl_succ(TAVL_nodeptr p);
	/*
	   Returns successor of "p", or NULL if "p" has no successor.
	 */

	TAVL_nodeptr tavl_pred(TAVL_nodeptr p);
	/*
	   Returns predecessor of "p", or NULL if no predecessor.
	 */

	int tavl_counter(TAVL_treeptr tree);
	void *tavl_node_data(TAVL_nodeptr p);

/**************      END PUBLIC DEFINITIONS     *******************/

#ifdef __cplusplus
}				/* extern "C" */
#endif				/* __cplusplus */
#endif				/* __TAVL_H__ */
